package subway;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
import java.io.File; // 添加这行
import java.io.FileReader; // 添加这行
public class SubwaySystem {
    // 地铁网络数据结构
    private Map<String, Station> stationMap = new HashMap<>(); // 站点名称 -> 站点对象
    private Map<String, List<String>> lineStations = new HashMap<>(); // 线路 -> 站点列表
    private Set<String> allLines = new HashSet<>(); // 所有线路

    // 加载地铁数据
    public void loadSubwayData(String filePath) throws IOException {
        File file = new File(filePath);
        
        // 检查文件是否存在
        if (!file.exists()) {
            throw new IOException("文件不存在: " + filePath);
        }
        
        // 检查是否为可读文件
        if (!file.canRead()) {
            throw new IOException("文件不可读: " + filePath);
        }
        
        try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            String line;
            String currentLine = null;
            
            // 读取文件的每一行
            while ((line = br.readLine()) != null) {
                line = line.trim();
                
                // 跳过空行
                if (line.isEmpty()) {
                    continue;
                }
                
                // 检测新线路标题行（例如："1号线站点间距"）
                if (line.matches("\\d+号线站点间距")) {
                    currentLine = line.replace("站点间距", "").trim();
                    allLines.add(currentLine);
                    lineStations.put(currentLine, new ArrayList<>());
                    
                    // 跳过标题行和列标题行
                    br.readLine(); // 跳过"站点名称"行
                    br.readLine(); // 跳过分隔线行
                    continue;
                }
                
                // 解析数据行
                if (currentLine != null && line.contains("---")) {
                    String[] parts = line.split("\t");
                    if (parts.length >= 2) {
                        String stations = parts[0];
                        String distanceStr = parts[1];

                        String[] stationPair = stations.split("---");
                        if (stationPair.length == 2) {
                            String stationA = stationPair[0].trim();
                            String stationB = stationPair[1].trim();
                            double distance = Double.parseDouble(distanceStr);

                            // 添加站点到线路
                            if (!lineStations.get(currentLine).contains(stationA)) {
                                lineStations.get(currentLine).add(stationA);
                            }
                            if (!lineStations.get(currentLine).contains(stationB)) {
                                lineStations.get(currentLine).add(stationB);
                            }

                            // 添加站点和边
                            addStationAndEdge(stationA, stationB, distance, currentLine);
                        }
                    }
                }
            }
        }
    }

    // 添加站点和边
    private void addStationAndEdge(String stationA, String stationB, double distance, String lineName) {
        // 获取或创建站点A
        Station a = stationMap.computeIfAbsent(stationA, k -> new Station(stationA));
        // 获取或创建站点B
        Station b = stationMap.computeIfAbsent(stationB, k -> new Station(stationB));

        // 添加双向边
        a.addNeighbor(b, distance, lineName);
        b.addNeighbor(a, distance, lineName);
    }
    // 功能1：识别所有中转站
    public Map<String, Set<String>> findTransferStations() {
        Map<String, Set<String>> result = new HashMap<>();

        // 遍历所有线路的站点
        for (Map.Entry<String, List<String>> entry : lineStations.entrySet()) {
            String line = entry.getKey();
            List<String> stations = entry.getValue();

            for (String station : stations) {
                // 添加线路到站点的线路集合
                result.computeIfAbsent(station, k -> new HashSet<>()).add(line);
            }
        }

        // 过滤出线路数 >= 2 的站点
        Iterator<Map.Entry<String, Set<String>>> it = result.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Set<String>> entry = it.next();
            if (entry.getValue().size() < 2) {
                it.remove();
            }
        }

        return result;
    }

    // 功能2：查找距离小于n的站点
    public List<NearbyStation> findNearbyStations(String startStationName, double maxDistance) {
        List<NearbyStation> result = new ArrayList<>();
        Station startStation = stationMap.get(startStationName);
        
        if (startStation == null) {
            throw new IllegalArgumentException("站点不存在: " + startStationName);
        }

        // 使用Dijkstra算法计算最短路径
        Map<Station, Double> distanceMap = new HashMap<>();
        PriorityQueue<StationDistance> pq = new PriorityQueue<>();
        
        // 初始化距离
        for (Station station : stationMap.values()) {
            distanceMap.put(station, Double.MAX_VALUE);
        }
        distanceMap.put(startStation, 0.0);
        pq.offer(new StationDistance(startStation, 0.0));

        // 记录每个站点的线路
        Map<Station, String> lineMap = new HashMap<>();

        while (!pq.isEmpty()) {
            StationDistance current = pq.poll();
            Station currentStation = current.station;
            double currentDist = current.distance;

            if (currentDist > distanceMap.get(currentStation)) {
                continue;
            }

            // 遍历邻居
            for (Edge edge : currentStation.edges) {
                Station neighbor = edge.to;
                double newDist = currentDist + edge.distance;

                if (newDist < distanceMap.get(neighbor) && newDist <= maxDistance) {
                    distanceMap.put(neighbor, newDist);
                    lineMap.put(neighbor, edge.line);
                    pq.offer(new StationDistance(neighbor, newDist));
                }
            }
        }

        // 收集结果
        for (Map.Entry<Station, Double> entry : distanceMap.entrySet()) {
            Station station = entry.getKey();
            double dist = entry.getValue();
            
            if (station != startStation && dist <= maxDistance) {
                result.add(new NearbyStation(
                    station.name, 
                    lineMap.getOrDefault(station, "未知线路"), 
                    dist
                ));
            }
        }

        return result;
    }

    // 功能3：查找所有路径
    public List<List<String>> findAllPaths(String startStationName, String endStationName) {
        List<List<String>> result = new ArrayList<>();
        Station start = stationMap.get(startStationName);
        Station end = stationMap.get(endStationName);
        
        if (start == null || end == null) {
            throw new IllegalArgumentException("站点不存在");
        }

        Set<Station> visited = new HashSet<>();
        List<String> path = new ArrayList<>();
        path.add(start.name);
        visited.add(start);

        findAllPathsDFS(start, end, visited, path, result);
        return result;
    }

    // 深度优先搜索查找所有路径
    private void findAllPathsDFS(Station current, Station end, Set<Station> visited, 
                                       List<String> path, List<List<String>> result) {
        if (current == end) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (Edge edge : current.edges) {
            Station neighbor = edge.to;
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                path.add(neighbor.name);
                
                findAllPathsDFS(neighbor, end, visited, path, result);
                
                // 回溯
                visited.remove(neighbor);
                path.remove(path.size() - 1);
            }
        }
    }

    // 功能4：查找最短路径
    public List<String> findShortestPath(String startStationName, String endStationName) {
        Station start = stationMap.get(startStationName);
        Station end = stationMap.get(endStationName);
        
        if (start == null || end == null) {
            throw new IllegalArgumentException("站点不存在");
        }

        // 使用Dijkstra算法计算最短路径
        Map<Station, Double> distanceMap = new HashMap<>();
        Map<Station, Station> prevMap = new HashMap<>();
        PriorityQueue<StationDistance> pq = new PriorityQueue<>();
        
        // 初始化距离
        for (Station station : stationMap.values()) {
            distanceMap.put(station, Double.MAX_VALUE);
            prevMap.put(station, null);
        }
        distanceMap.put(start, 0.0);
        pq.offer(new StationDistance(start, 0.0));

        while (!pq.isEmpty()) {
            StationDistance current = pq.poll();
            Station currentStation = current.station;
            double currentDist = current.distance;

            if (currentStation == end) {
                break;
            }

            if (currentDist > distanceMap.get(currentStation)) {
                continue;
            }

            // 遍历邻居
            for (Edge edge : currentStation.edges) {
                Station neighbor = edge.to;
                double newDist = currentDist + edge.distance;

                if (newDist < distanceMap.get(neighbor)) {
                    distanceMap.put(neighbor, newDist);
                    prevMap.put(neighbor, currentStation);
                    pq.offer(new StationDistance(neighbor, newDist));
                }
            }
        }

        // 构建路径
        List<String> path = new ArrayList<>();
        Station current = end;
        while (current != null) {
            path.add(current.name);
            current = prevMap.get(current);
        }
        Collections.reverse(path);
        
        return path;
    }

    // 功能5：打印简洁路径
 // 打印简洁路径（最终改进版）
    public void printConcisePath(String start, String end) {
        List<String> path = findShortestPath(start, end);
        if (path.isEmpty()) {
            System.out.println("无法找到从" + start + "到" + end + "的路径");
            return;
        }

        System.out.print("从" + start + "到" + end + "的简洁路径：");
        
        // 处理直达情况（无需换乘）
        if (path.size() == 2) {
            String line = findLineBetweenStations(start, end);
            if (line != null) {
                System.out.println("乘坐" + line + "直达" + end);
                return;
            }
        }

        // 处理需要换乘的情况
        String currentLine = null;
        String startStation = start;
        String prevStation = start;
        
        for (int i = 1; i < path.size(); i++) {
            String currentStation = path.get(i);
            
            // 查找前一站到当前站的线路
            String line = findLineBetweenStations(prevStation, currentStation);
            
            // 如果是路径中的第一站，初始化当前线路
            if (currentLine == null) {
                currentLine = line;
            } 
            // 如果发现线路变化，说明是换乘站
            else if (!currentLine.equals(line)) {
                // 输出当前线路段
                System.out.print("乘坐" + currentLine + "到" + prevStation);
                
                // 输出换乘信息
                System.out.print("，换乘");
                currentLine = line;
                startStation = prevStation;
            }
            
            prevStation = currentStation;
        }
        
        // 输出最后一段线路
        System.out.println(currentLine + "到" + end);
    }

    // 辅助方法：获取两站之间的线路
    private String findLineBetweenStations(String from, String to) {
        Station station = stationMap.get(from);
        if (station == null) return null;
        for (Edge edge : station.getEdges()) {
            if (edge.getTo().getName().equals(to)) {
                return edge.getLine();
            }
        }
        return null;
    }

    // 功能6：计算普通单程票费用
    public double calculateFare(List<String> path) {
        if (path.size() < 2) return 0.0;
        
        double totalDistance = 0.0;
        for (int i = 0; i < path.size() - 1; i++) {
            String from = path.get(i);
            String to = path.get(i + 1);
            totalDistance += getDistanceBetweenStations(from, to);
        }

        // 武汉地铁票价规则（示例）：
        // 0-9公里：2元；9-14公里：3元；14-21公里：4元；21-30公里：5元；30公里以上每10公里加1元
        if (totalDistance <= 9) return 2.0;
        else if (totalDistance <= 14) return 3.0;
        else if (totalDistance <= 21) return 4.0;
        else if (totalDistance <= 30) return 5.0;
        else {
            int extra = (int) Math.ceil((totalDistance - 30) / 10);
            return 5.0 + extra;
        }
    }

    // 辅助方法：获取两站距离
    private double getDistanceBetweenStations(String from, String to) {
        Station station = stationMap.get(from);
        if (station == null) return 0.0;
        for (Edge edge : station.getEdges()) {
            if (edge.getTo().getName().equals(to)) {
                return edge.getDistance();
            }
        }
        return 0.0; // 若两站不相邻，返回0（需根据业务逻辑处理）
    }
    // 功能7：计算武汉通费用
    public double calculateWuhanTongFare(List<String> path) {
        double normalFare = calculateFare(path);
        // 武汉通9折优惠
        return normalFare * 0.9;
    }

    // 功能7：计算日票费用
    public double calculateDayTicketFare(List<String> path) {
        // 日票费用为0元（已购买日票）
        return 0.0;
    }
}    

